//
// Created by 98770 on 2022/11/21.
//

#include "huffman_tree.h"

struct Unit {
    int weight;
    int lchild;
    int rchild;
    int parent;
    char ch;
};

void ShowInstructions() {
    printf("Welcome To Huffman Complier!!!\n");
    printf("Please add Information You Wanner to Encode in ToBeTran.txt\n");
    printf("Which should be located in the same folder as this program\n");
    printf("After init or load , use f to free memory\n");
    printf("h to get help\ni to init\ns to save\nl to load\nv to show\nd to decode\ne to encode\nf to free\nq to exit\n");
}

void show_huffman_tree(Huffman_Tree t, int node, int n) {
    int i;
    if (node == -1)
        node = t[0].weight * 2 - 1;
    if (node != 0) {
        show_huffman_tree(t, t[node].rchild, n + 1);
        for (i = 0; i < n; i++) {
            printf("\t");
        }
        printf("%2c\n", t[node].ch);
        show_huffman_tree(t, t[node].lchild, n + 1);
    }
}

void Encode(Huffman_Tree t) {
    if (t == NULL) {
        printf("Null Tree!\n");
        return;
    }
    FILE *fp = fopen("ToBeTran.txt", "r");
    FILE *new = fopen("CodeFile.txt", "w");
    if (fp == NULL || new == NULL) {
        printf("File Error\n");
        return;
    }
    char buf;
    int n = t[0].weight;
    int i;
    int k;
    char *cd = malloc(sizeof(char) * (n + 1));
    memset(cd, '\0', sizeof(cd[0]) * (n + 1));
    while (fscanf(fp, "%c", &buf) != EOF) {
        i = 1;
        while (t[i].ch != buf) {
            i++;
        }
        if(i>n){
            printf("char not found in tree!\n");
            break;
        }
        k = 0;
        while (t[i].parent != 0) {
            if (t[t[i].parent].lchild == i)
                cd[k++] = 0;
            else
                cd[k++] = 1;
            i = t[i].parent;
        }
        for (int j = k - 1; j >= 0; --j) {
            fprintf(new, "%d", cd[j]);
        }
        fprintf(new, "%c", ' ');
    }
    fclose(fp);
    fclose(new);
    free(cd);
    if(i<=n)
        printf("Encode finished!\n");
}

void Decode(Huffman_Tree t) {
    if (t == NULL) {
        printf("Null Tree!\n");
        return;
    }
    int root = t[0].weight * 2 - 1;
    FILE *fp = fopen("CodeFile.txt", "r");
    FILE *new = fopen("TextFile.txt", "w");
    if (fp == NULL || new == NULL) {
        printf("File Error\n");
        return;
    }
    char buf[1024];
    memset(buf, '\0', sizeof(buf[0]) * 1024);
    while (fscanf(fp, "%s ", buf) != EOF) {
        int i = 0;
        int f = root;
        while (buf[i] != '\0') {
            if (buf[i] == '1')
                f = t[f].rchild;
            else
                f = t[f].lchild;
            i++;
        }
        fprintf(new, "%c", t[f].ch);
        memset(buf, '\0', sizeof(buf[0]) * 1024);
    }
    fclose(fp);
    fclose(new);
    printf("Decode finished!\n");
}

int save_tree(Huffman_Tree ori) {
    if (ori == NULL) {
        printf("Null Tree!\n");
        return ERROR;
    }
    FILE *fp = fopen("htmtree.txt", "w");
    if (fp == NULL)
        return ERROR;
    int n = ori[0].weight;
    int m = 2 * n - 1;
    fprintf(fp, "%d ", n);
    for (int i = 1; i <= m; i++) {
        fprintf(fp, "%d  %d  %d  %d  %c ", ori[i].weight, ori[i].lchild, ori[i].rchild, ori[i].parent, ori[i].ch);
    }
    fclose(fp);
    printf("Tree Saved!\n");
    return OK;
}

Huffman_Tree load_tree() {
    FILE *fp = fopen("htmtree.txt", "r");
    char *buff[255];
    int val;
    int i;
    if (fp == NULL)
        return NULL;
    int n, m;
    fscanf(fp, "%d", &n);
    m = 2 * n - 1;
    Huffman_Tree t = malloc(sizeof(HTNode) * (m + 1));
    t[0].weight = n;
    for (i = 1; i <= m; i++) {
        for (int k = 1; k <= 4; k++) {
            memset(buff, '\0', sizeof(buff));
            fscanf(fp, "%s ", buff);
            val = atoi(buff);
            switch (k) {
                case 1:
                    t[i].weight = val;
                    break;
                case 2:
                    t[i].lchild = val;
                    break;
                case 3:
                    t[i].rchild = val;
                    break;
                case 4:
                    t[i].parent = val;
                    break;
                default:
                    break;
            }
        }
        fscanf(fp, "%c", &(t[i].ch));
    }
    printf("Load Tree Finished!\n");
    return t;
}

void Select(Huffman_Tree ori_buf, int arrange, int *s1, int *s2) {
    int temp;
    int i, k;
    for (i = 1; i <= arrange; i++)
        if (ori_buf[i].parent == 0) {
            temp = ori_buf[i].weight;
            *s1 = i;
            break;
        }
    for (k = 1; k <= arrange; k++) {
        if (ori_buf[k].parent == 0 && ori_buf[k].weight < temp) {
            temp = ori_buf[k].weight;
            *s1 = k;
        }
    }
    for (i = 1; i <= arrange; i++)
        if (ori_buf[i].parent == 0 && i != *s1) {
            temp = ori_buf[i].weight;
            *s2 = i;
            break;
        }
    for (k = 1; k <= arrange; k++) {
        if (ori_buf[k].parent == 0 && ori_buf[k].weight < temp && k != *s1) {
            temp = ori_buf[k].weight;
            *s2 = k;
        }
    }
}

Huffman_Tree init_huffman_tree(Huffman_Tree ori_buf) {
    //Read inneed data and store then in struct array
    int n;
    printf("Input amount then ch and priority like 3 a1b2c3\n");
    scanf("%d ", &n);
    if (n <= 1) {
        ori_buf = NULL;
        return NULL;
    }
    int m = 2 * n - 1;
    int i;
    ori_buf = malloc(sizeof(HTNode) * (m + 1));
    if (ori_buf == NULL)
        return NULL;
    ori_buf[0].weight = n;
    for (i = 1; i <= m; ++i) {
        if (i <= n) {
            scanf("%c%d", &(ori_buf[i].ch), &(ori_buf[i].weight));
            ori_buf[i].lchild = ori_buf[i].rchild = ori_buf[i].parent = 0;
        }
        else {
            ori_buf[i].lchild = ori_buf[i].rchild = ori_buf[i].parent = ori_buf[i].weight = 0;
            ori_buf[i].ch = '$';
        }
    }
    int s1, s2;
    for (int i = n + 1; i <= m; ++i) {
        Select(ori_buf, i - 1, &s1, &s2);
        ori_buf[s1].parent = i;
        ori_buf[s2].parent = i;
        ori_buf[i].lchild = s1;
        ori_buf[i].rchild = s2;
        ori_buf[i].weight = ori_buf[s1].weight + ori_buf[s2].weight;
    }
    printf("Init Finished!\n");
    return ori_buf;
}

void free_tree(Huffman_Tree T) {
    if (T != NULL) {
        printf("Free the memory!\n");
        free(T);
    }
    else
        printf("Already Null\n");
}
